public class Main {
    public static void main(String[] args) {
        // 乱序
        int[] arr = new int[]{8, 3, 5, 1, 4, 2, 7, 6};
        // 倒序
        int[] arr1 = new int[]{9,8,7,6,5,4,3,2,1,0};
        // 顺序
        int[] arr2 = new int[]{0,1,2,3,4,5,6,7,8,9};
        shellSort(arr);
        for(int e: arr) {
            System.out.print(e + " ");
        }
    }

    public static void insertSort(int[] arr) {
        /**
         * 直接插入排序手动实现*/
        int n = arr.length;
        for(int i = 1; i < n; i++) {
            int j = i - 1;
            int temp = arr[i];
            while(j >= 0 && arr[j] > temp) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
    }

    public static void shellSort(int[] arr) {
        /**
         * 希尔排序手动实现
         * 仅枚举增量，从arr.length/2开始枚举，每次除2，直至1*/
        int gap = arr.length / 2;
        while(gap >= 1) {
            shell(arr, gap);
            gap /= 2;
        }
    }

    private static void shell(int[] arr, int gap) {
        /**
         * 希尔排序不同增量预排序实现*/
        int n = arr.length;
        for(int i = gap; i < 2*gap; i++) { // -枚举起始位置
            // 直接插入排序
            for(int j = i; j < n; j+=gap) {
                int prev = j - gap;
                int temp = arr[j];
                while(prev >= 0 && arr[prev] > temp) {
                    arr[prev + gap] = arr[prev];
                    prev -= gap;
                }
                arr[prev + gap] = temp;
            }
        }
    }
}
